package _18_剑指OfferII;

import _18_剑指OfferII.datastrcute.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class _050_剑指OfferII向下的路径节点之和 {

    // 递归寻找，每哥节点都当作根节点，这样就是完全便利，接下来就一定会找到想要的值
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;

        int ans = pathSum(root, 0, targetSum);

        ans += pathSum(root.left, targetSum);
        ans += pathSum(root.left, targetSum);
        return ans;
    }

    private int pathSum(TreeNode root, int prevTotal, int target) {
        if (root == null) return 0;
        prevTotal += root.val;
        int ans = target == prevTotal? 1: 0;

        ans += pathSum(root.left, prevTotal, target);
        ans += pathSum(root.right, prevTotal, target);
        return ans;
    }


    // 分析题目可知， 前缀和可能出现多种情况，所以需要一个计数的
    Map<Integer, Integer> map = new HashMap<>();

    public int pathSum1(TreeNode root, int targetSum) {
        map.put(0, 1);
        return pathSum1(root, 0, targetSum);
    }

    private int pathSum1(TreeNode root, int prevTotal, int target) {
        if (root == null) return 0;
        prevTotal += root.val;
        int ans = map.getOrDefault(prevTotal - target, 0);
        map.put(prevTotal, map.getOrDefault(prevTotal, 0) + 1);
        ans += pathSum1(root.left, prevTotal, target);
        ans += pathSum1(root.right, prevTotal, target);
        map.put(prevTotal, map.getOrDefault(prevTotal, 0) - 1);
        return ans;
    }


}
